package com.cqs.leetcode.ds.union.find;

public class WeightQuickUnion implements IUnionFind {

    private int ids[];//父链接数组【触点索引】
    private int weight[];//权重
    private int count;//计数


    public WeightQuickUnion(int n) {
        this.count = n;
        ids = new int[n];
        weight = new int[n];
        for (int i = 0; i < n; i++) {
            ids[i] = i;
            weight[i] = 1;
        }
    }

    @Override
    public int find(int p) {
        while (p != ids[p]) {
            p = ids[p];
        }
        return p;
    }

    @Override
    public void union(int p, int q) {
        int proot = find(p);
        int qroot = find(q);
        if (proot == qroot) return;
        if (weight[proot] <= weight[qroot]) {
            ids[qroot] = proot;
            weight[proot] += weight[qroot];
        } else {
            ids[proot] = qroot;
            weight[qroot] += weight[proot];
        }
        --count;

    }

    @Override
    public int count() {
        return count;
    }

    @Override
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }
}
